package main.java.indi.zyj.coderecord;

import main.java.indi.zyj.hot100.base.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class BuildTree {

    Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        int len = inorder.length;
        indexMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            indexMap.put(inorder[i], i);
        }

        return myBuildTree(inorder, postorder, 0, len - 1, 0, len - 1);

    }

    private TreeNode myBuildTree(int[] inorder, int[] postorder, int inLeft, int inRight, int postLeft, int postRight) {

        if (inLeft > inRight || postLeft > postRight) {  // 不满足，说明没有元素，返回空树
            return null;
        }

        // 找到中序遍历的根节点
        int rootNode = postorder[postRight];

        // 找到中序遍历根节点的下标
        int rootNodeIndex = indexMap.get(rootNode);

        // 找到左右两子树的长度
        int leftLen = rootNodeIndex - inLeft;

        // 建立根节点
        TreeNode treeNode = new TreeNode(rootNode);
        treeNode.left = myBuildTree(inorder, postorder, inLeft, rootNodeIndex, postLeft, postLeft + leftLen - 1);
        treeNode.right = myBuildTree(inorder, postorder, rootNodeIndex + 1, inRight, postLeft + leftLen, postRight - 1);
        return treeNode;

    }


}
